package com.hy.dp.bagProblem.fullBag;

import java.util.Arrays;
import java.util.List;

public class WordSplitting {


    /**
     *
     * 139.单词拆分
     * 力扣题目链接
     *
     * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
     *
     * 说明：
     *
     * 拆分时可以重复使用字典中的单词。
     *
     * 你可以假设字典中没有重复的单词。
     *
     * 示例 1： 输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
     *
     * 思路
     * 看到这道题目的时候，大家应该回想起我们之前讲解回溯法专题的时候，讲过的一道题目回溯算法：分割回文串，就是枚举字符串的所有分割情况。
     *
     * 回溯算法：分割回文串：是枚举分割后的所有子串，判断是否回文。
     *
     * 本道是枚举分割所有字符串，判断是否在字典里出现过。
     *
     * 背包问题
     * 单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
     *
     * 拆分时可以重复使用字典中的单词，说明就是一个完全背包！
     *
     * 动规五部曲分析如下：
     *
     * 1.确定dp数组以及下标的含义
     * dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
     *
     * 2.确定递推公式
     * 如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
     * 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
     *
     * 3.dp数组如何初始化
     * 从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]一定要为true，否则递归下去后面都都是false了。
     *
     * 那么dp[0]有没有意义呢？
     *
     * dp[0]表示如果字符串为空的话，说明出现在字典里。
     *
     * 但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。
     *
     * 下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
     *
     * 4.确定遍历顺序
     * 题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。
     *
     * 还要讨论两层for循环的前后循序。
     *
     * 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
     *
     * 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
     * 5.举例推导dp[i]
     * 以输入: s = "leetcode", wordDict = ["leet", "code"]为例，dp状态如图：
     *
     * 0    1   2   3   4   5   6   7   8
     * 1    0   0   0   1   0   0   0   1
     *
     * @param word
     * @param wordArr
     * @return
     */
    public static boolean wordSplit(String word, List<String> wordArr){
        //1. 确定dp数组以及下标含义
        boolean [] dp = new boolean[word.length() + 1];
        //2.推导 递推式

        //3. dp数组初始化
        dp[0] = true;

        //4. 循环遍历  先背包   再物品
        for (int i = 1; i <= word.length(); i++) {
            for (int j = 0; j < i; j++) {
                // 截取字符串
                if (wordArr.contains(word.substring(j,i)) && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[word.length()];
    }

    public static void main(String[] args) {
        String word = "leetcode";
        List<String> wordArr = Arrays.asList(new String[]{"leet", "code"});
        System.out.println("res: "+ wordSplit(word,wordArr));

    }
}
